Problem :

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1 :

**Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]**

Example 2 :

**Input: root = [1]
Output: [[1]]**

Example 3 :

**Input: root = []
Output: []**

核心思維 :

初始化陣列並儲存每一層節點的值，利用佇列遍歷二元樹

1. 若根節點為空則回傳空的結果
2. 若根節點不為空，將根節點放入佇列中，並進行遍歷以計算和儲存當前所處層節點數量的值。
3. 遍歷當前所處層的所有節點，取出佇列的前端節點，若該節點的左子節點不為空，則將左子節點加入佇列，若該節點的右子節點不為空，則將右子節點加入佇列。
4. 將當前節點的值添加至當前層節點的值中，並將當前層節點的值添加到結果中
5. 回傳結果

程式碼 :

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        //將陣列初始化，並儲存每一層節點的值
        vector<vector<int>> result;
        //利用佇列遍歷二元樹
        queue<TreeNode*> q;
        //若根節點為空則回傳空的結果
        if(root == nullptr){
            return result;
        }
        //將根節點放入佇列當中
        q.push(root);
        //當佇列不為空的時候，繼續進行遍歷
        while(!q.empty()){
            //計算並儲存當前所處層的節點數量的值
            int size = q.size();
            vector<int>level;
            //遍歷當前所處層的所有節點
            for(int i = 0; i < size; i++){
                //取出佇列的前端節點
                TreeNode* node = q.front();
                q.pop();
                //若該節點的左子節點不為空，則將左子節點加入佇列
                if(node -> left != nullptr){
                q.push(node -> left);
                }
                //若該節點的右子節點不為空，則將右子節點加入佇列
                if(node -> right != nullptr){
                    q.push(node -> right);
                }
                //將當前節點的值添加至當前層節點的值中
                level.push_back(node -> val);
            }
            //將當前層節點的值添加到結果中
            result.push_back(level);
        }
        //回傳結果
        return result;
    }    
};

結論 :

在這題當中，我們學習如何在二元樹當中進行遍歷並計算和儲存節點數量的值，其中需要將空的子節點隔開進行以完成二元樹，此外遍歷過程的設計與應用可以決定建構分析二元樹的效率，因此對二元樹的結構和排序方式的理解是在解這題時相當重要的一部分。